using namespace std;
#include<algorithm>
#include<iostream>
#include<vector>
class Solution1
{
public:
    vector<vector<int>> generate(int numRows)
    {
        vector<vector<int>> vv(numRows);
        for (int i = 0; i < numRows; i++)
        {
            vv[i].resize(i + 1, 1);
        }
        for (int i = 0; i < numRows; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (j == 0 || j == i)
                {
                    vv[i][j] = 1;
                }
                else
                {
                    vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
                }
            }
        }
        return vv;
    }
};
class Solution2
{
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        int maxi = 0, mini = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] >= nums[maxi]) maxi = i;
            if (nums[i] <= nums[mini]) mini = i;
        }
        vector<int> count(nums[maxi] - nums[mini] + 1, 0);
        vector<int> v(2, 1);
        int index = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            count[nums[i] - nums[mini]]++;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (count[nums[i] - nums[mini]] == 1)
            {
                v[index++] = nums[i];
            }
        }
        return v;
    }
};
class Solution3
{
public:
    int singleNumber(vector<int>& nums)
    {
        int len = nums.size();
        sort(nums.begin(), nums.end());
        int i = 0;
        while (i < len)
        {
            if (i + 1 >= len) return i;
            if (nums[i] != nums[i + 1])
            {
                return i;
            }
            else
            {
                i += 3;
            }
        }
    }
};

void quicksort(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int keyi = left;
    int begin = left;
    int end = right;
    while (begin < end)
    {
        while (a[end] > a[keyi])
        {
            end--;
        }
        while (a[begin] < a[keyi])
        {
            begin++;
        }
        swap(a[begin], a[end]);
    }
    swap(a[keyi], a[begin]);
    quicksort(a, left, begin);
    quicksort(a, begin+1, right);
    
}
int main()
{
    Solution3 a;
    vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(0);
    v.push_back(1);
    v.push_back(0);
    v.push_back(1);
    v.push_back(99);

    int ret=a.singleNumber(v);
    int arr[] = { 4214,546,43634,7137,3254,5132,21,6346,3 };
    quicksort(arr,0,8);
    for (int i = 0; i < 9; i++)
    {
        cout << arr[i] << endl;
    }
    return 0;
}